import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    public long subArrayRanges(int[] nums) {
        int len=nums.length;
        int sum=0;
        for(int i=0;i<len-1;i++){
            int min=nums[i];
            int max=nums[i];
            for(int j=i+1;j<len;j++){
                min=Math.min(min,nums[j]);
                max=Math.max(max,nums[j]);
                sum+=max-min;
            }
        }
        return sum;
    }














    public int maxChunksToSorted(int[] arr) {
        int max=0;
        int sum=0;
        for(int i=0;i<arr.length;i++){
            max=Math.max(max,arr[i]);
            if(max==i){
                sum++;
            }
        }
        return sum;
    }



















    public TreeNode bstFromPreorder(int[] preorder) {
        int len=preorder.length;
        if(len==0){
            return null;
        }
        return dfs(preorder,0,len-1);
    }
    public TreeNode dfs(int[] arr,int left,int right){
        if(left>right){
            return null;
        }
        TreeNode root=new TreeNode(arr[left]);
        if(left==right){
            return root;
        }
        int l=left;
        int r=right;
        while (l<r){
            int mid=l+(r-l+1)/2;
            if(arr[mid]<arr[left]){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        TreeNode leftT=dfs(arr,left+1,l);
        TreeNode rightT=dfs(arr,l+1,right);
        root.left=leftT;
        root.right=rightT;
        return root;
    }

















    public String smallestSubsequence(String s) {
        char[] str=s.toCharArray();
        int len=s.length();
        int[] arr=new int[26];
        for (int i = 0; i < len; i++) {
            arr[str[i]-'a']=i;
        }
        boolean[] booleans=new boolean[26];
        Deque<Character> deque=new ArrayDeque<>();
        for(int i=0;i<len;i++){
            if(booleans[str[i]-'a']){
                continue;
            }
            while (!deque.isEmpty()&&deque.peekLast()>str[i]&&arr[deque.peekLast()-'a']>i){
                char ch=deque.removeLast();
                booleans[ch-'a']=false;
            }
            deque.addLast(str[i]);
            booleans[str[i]-'a']=true;
        }
        StringBuffer sb=new StringBuffer();
        for(char ch : deque){
            sb.append(ch);
        }
        return sb.toString();
    }

















    public String removeDuplicateLetters(String s) {
        int len=s.length();
        int[] arr=new int[26];
        char[] str=s.toCharArray();
        for (int i = 0; i < len; i++) {
            arr[str[i]-'a']=i;
        }
        boolean[] booleans=new boolean[26];
        Deque<Character> deque=new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            if(booleans[str[i]-'a']){
                continue;
            }
            while (!deque.isEmpty()&&deque.peekLast()>str[i]&&arr[deque.peekLast()-'a']>i){
                char ch=deque.removeLast();
                booleans[ch-'a']=false;
            }
            booleans[str[i]-'a']=true;
            deque.addLast(str[i]);
        }
        StringBuilder sb=new StringBuilder();
        for(char ch : deque){
            sb.append(ch);
        }
        return sb.toString();
    }
}
